package leetcode.p1171;

import java.util.*;

/**
 * @author: trtan
 * @date: 2021-07-07 19:05
 **/
public class CountGoodMeals {
    /**
     * 枚举、计数、二进制
     * @param deliciousness
     * @return int
     * @author trtan
     * @date 2021/7/7 19:19
     */
    public int countPairs(int[] deliciousness) {
        final int Mod = (int) 1e9 + 7;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < deliciousness.length; i++) {
            Integer count = cnt.getOrDefault(deliciousness[i], 0);
            cnt.put(deliciousness[i], count + 1);
        }
        List<Integer> list = new ArrayList<>(cnt.keySet());
        Collections.sort(list);
        long ans = 0;
        for (int i = 0; i < list.size(); i++) {
            int key = list.get(i);
            int value = cnt.get(key);
            for (int j = 0; j <= 21; j++) {
                int x = (1 << j) - key;
                if (x < 0 || x < key) {
                    continue;
                }
                if (x == key) {
                    ans = (ans + (long)value * (long)(value - 1) / 2) % Mod;
                } else {
                    int y = cnt.getOrDefault(x, 0);
                    System.out.println(key + ", " + x + ", " + value + ", " + y);
                    ans = (ans + (long) value * (long) y) % Mod;
                }
            }
        }
        return (int) ans;
    }
}
